package libnetdb.dm.assoc.base;
import java.util.*;
import java.io.*;

/**
 * <p><code>Itemset</code> defines the abstract concept of
 * transactions. Specifically, <code>Itemset</code> is a set of
 * items. In our implementation, each item is represented by
 * an integer, thus, the itemset is an array of integers. One can
 * access this array by the public member <code>ids[]</code>.</p>
 *
 * <p>This interface also provides several basic operation of the
 * itemset, includes merging two itemsets, subtract the elements of
 * one itemset from another itemset, testring if one itemset is a
 * subset of the other itemset, and etc.</p>
 *
 * @author Cheng-Ru Lin
 * @version 1.0
 */
public class Itemset implements Cloneable, Serializable, Comparable{

    /**
     * The integer array representing the items in this itemset. It
     * should be noted that the elements in this array should be
     * unique and sorted.
     */
    public int ids[];

    /**
     * Returns a new Itemset which is the result of merging the two
     * specified itemsets. If itemset A is [1,2,3,4] and itemset B
     * is [3,4,5,6], then the merging result of itemset A and B is
     * [1,2,3,4,5,6].
     *
     * @param a the first itemset to be merged
     * @param b the second itemset to be merged
     * @return the merged itemset
     */
    public static Itemset merge(Itemset a, Itemset b){
        int tmp[] = new int[a.size()+b.size()], i=0, j=0, n=0;
        while(i<a.size()&&j<b.size()){
            if(a.ids[i]==b.ids[j]){
                tmp[n++] = a.ids[i++];
                j++;
            }else tmp[n++] = a.ids[i]<b.ids[j]? a.ids[i++]:b.ids[j++];
        }
        return new Itemset(tmp, n);
    }

    /**
     * Returns a new Itemset which is the result of moving all the
     * elements in the second itemset from the first itemset. For
     * example, if itemset A is [1,2,3,4] and itemset B is [3,4,5,6],
     * then the result of substract B from A is [1,2].
     *
     * @param a the itemset to be subtracted
     * @param b the itemset of which the elements will be removed
     *   from the first itemset
     * @return the subtracted itemset
     */
    public static Itemset subtract(Itemset a, Itemset b){
        int tmp[] = new int[a.size()], i=0, n=0;
        for(int j=0; j < b.size(); j++){
            while(i < a.size() && a.ids[i] < b.ids[j]) tmp[n++] = a.ids[i++];
            if(i < a.size() && a.ids[i] == b.ids[j]) i++;
        }
        while(i < a.size()) tmp[n++] = a.ids[i++];
        return new Itemset(tmp, n);
    }

    /**
     * Constructs a new allocated itemset from the specified
     * collection. Each element in that collection should be type of
     * <code>Integer</code>. Note that the elements in the collection
     * could be unsorted.
     *
     * @param c the collection contains the integers which make up
     *   the new <code>Itemset</code>
     */
    public Itemset(Collection c){
        ids = new int[c.size()];
        int index = 0;
        for(Iterator it = c.iterator();it.hasNext();)
            ids[index++] = ((Integer)it.next()).intValue();
        Arrays.sort(ids);
    }

    /**
     * Constructs a new allocated itemset with those elements
     * specified in the given int array. Note that the elements in
     * the integer array, <code>item</code>, could be unsorted.
     *
     * @param items an integer array consists of the elements which
     *   make up the new <code>Itemset</code>
     */
    public Itemset(int items[]) {
        ids = new int[items.length];
        for(int i=0;i<ids.length;i++)
            ids[i] = items[i];
        Arrays.sort(ids);
    }

    /**
     * Constructs a new allocated itemset with those elements
     * specified in the first <code>n</code> elements of the
     * given int array. Note that the elements in the integer array
     * could be unsorted.
     *
     * @param items an integer array, the first <code>n</code>
     *   elements in which will make up the new <code>Itemset</code>
     * @param n specified the number of elements to be considered
     */
    public Itemset(int items[], int n){
        ids = new int[n];
        for(int i=0;i<n;i++) ids[i] = items[i];
        Arrays.sort(ids);
    }

    /**
     * Gets the size of this itemset.
     *
     * @return the number of elements of this itemset
     */
    public int size(){
        return ids.length;
    }

    /**
     * Tests if the specified id exists in this itemset.
     *
     * @param id the integer to be tested
     * @return true if <code>id</code> is in this itemset; flase,
     *   otherwise.
     */
    public boolean contains(int id){
        int start = 0, end = ids.length-1;
        for(int x=(start+end)/2; start<=end; x=(start+end)/2){
            if(ids[x] < id) start = x+1;
            else if(ids[x] > id) end = x-1;
            else return true;
        }
        return false;
    }

    /**
     * Test if the specified itemset is a subset of this itemset.
     * For example, [1,2,3] is a subset of [1,2,3,4] but is not a
     * subset of [1,2,4,5].
     *
     * @param itemset the itemset to be test
     * @return true if the specified itemset is an subset of this
     *   itemset; flase otherwise.
     */
    public boolean contains(Itemset itemset){
        if(itemset.size()<=size()){
            for(int i=0;i<itemset.ids.length;i++)
                if(!contains(itemset.ids[i])) return false;
            return true;
        }else return false;
    }

    public Object clone(){
        return new Itemset(ids);
    }

    public int hashCode(){
        int code = 0x03175134;
        for(int i=0;i<ids.length;i++)
            code ^= (code * ids[0] + 0x9213874F);
        return code;
    }

    public boolean equals(Object obj){
        if(obj instanceof Itemset){
            Itemset itemset = (Itemset) obj;
            if(itemset.ids.length != ids.length) return false;
            for(int i=0;i<ids.length;i++)
                if(itemset.ids[i]!=ids[i]) return false;
            return true;
        }else return false;
    }

    public int compareTo(Object obj){
        Itemset itemset = (Itemset) obj;
        if(itemset.size()==size()){
            for(int i=0;i<ids.length;i++)
                if(itemset.ids[i]!=ids[i]) return ids[i]-itemset.ids[i];
            return 0;
        }else return size()-itemset.size();
    }

    /**
     * Returns a new <code>Itemset</code> which is the result of
     * substracting the element in the specified itemset from this
     * itemset.
     *
     * @param itemset the elements of which to be removed
     * @return the subtract result
     */
    public Itemset subtract(Itemset itemset){
        return subtract(this, itemset);
    }

    /**
     * Return a new <code>Itemset</code> which is the result of merging
     * the specified itemset and this itemset.
     *
     * @param itemset the elements of which to be merged
     * @return the merged result
     */
    public Itemset merge(Itemset itemset){
        return merge(this, itemset);
    }

    public String toString(){
        StringBuffer strbuf = new StringBuffer("[");
        if(ids.length>0) strbuf.append(ids[0]);
        for(int i=1;i<ids.length;i++)
            strbuf.append(", " + ids[i]);
        strbuf.append("]");
        return strbuf.toString();
    }
}